perm filename LISP1.OLD[LSP,JRA]1 blob
sn#073086 filedate 1973-11-20 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00014 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 LISP - a high-level mathematical language for data structures.
C00006 00003 Our primitive domain consists of objects called atoms or atomic symbols.
C00008 00004 Examples: S-exprs not S-exprs
C00010 00005
C00013 00006 We have two functions for traversing binary trees. They are both partial functions
C00015 00007 We cannot generate a very exciting theory based simply on car, cdr, and cons
C00018 00008
C00021 00009 Here's an intuitive description of such a function (predicate named equal).
C00023 00010 LIST NOTATION
C00027 00011 Problems
C00030 00012 V Use the following definition:
C00032 00013 VIII Use the following defintion:
C00034 00014
C00035 ENDMK
C⊗;
LISP - a high-level mathematical language for data structures.
Just as it is unnecessary to learn machine language to study numerical
algorithms, it is also unnecessary to learn machine language to understand
non-numerical processes. The distinction we are making is between data-
structures and storage structures. That is, data structures are independent
of how they are implemented on a machine. Data structures are representations
of information chosen to exhibit certain ordering and accessibility relation-
ship between data structures. Certainly in the real world you cannot ignore
storage structures when you are deciding upon the data structures which
will encode your problem, but the interesting aspects of representation of
information can be discussed at the level of data structures with no loss
of generality. The mapping of data structures to storage structures is
machine dependent anyway, and consists of bit-pushing, trickery and black
magic. A very crucial problem in data structures and algorithms is the
interplay between the representation and the algorithm: if you pick a
frugal representation prhaps your accessing algorithms become more time
consuming or the algorithm become less general. We will study this
interrelation carefully in this course.
If you take a course in elementary number theory or better yet recursive
function theory, you would begin with a precise description of the domain
of interest (the non-negative integers perhaps, or 0 and the successor
function) and then describe the class of functions or operations which will
be allowed in the developing theory. We will do the same.
Our primitive domain consists of objects called atoms or atomic symbols.
In computer science terminolgy they are either identifiers or numbers; i.e.
<atom> :: = <identifier>|<number>
<identifier> :: = <letter>|<identifier><letter>|<identifier><digit>
<number> :: = <digit>|<number><digit>
<letter> :: = A|B|C...|Z
<digit> :: = 0|1|2....
For example: atoms not atoms
ABC123 2a
12 a
A4D6 %%g
NIL ABD.
T (A . B)
Using an operator to be described later, we are able to enlarge on
this primitive domain obtaining the domain of interest for LISP functions,
that is the class of Symbolic expressions or S-expressions or also called
S-exprs. S-exprs include as a proper subset the atoms, but S-exprs can be
constructed of other S-exprs as follows: a left-paren followed by an
S-expr, followed by a period, followed by an S-expr, followed by a
period, followed by an S-expr, followed by a right-paren is also an S-expr.
To make everyone happy here's a BNF definition of S-expr
<sexpr> :: = <atom>|(<sexpr> . <sexpr>)|( )
We added "( )" as an S-expr for a reason which will become clear later.
Examples: S-exprs not S-exprs
A A . B
(A . B) (A . B . C)
(((A.B) .C) . (A.B)) ((A . B)))
Non-atomic sexprs are also called "dotted-pairs". S-exprs have a natural
interpretation as binary trees. A binary tree is a branching structure
consisting of a single root node and perhaps a collection of terminal
and non-terminal nodes. From non-terminal nodes we sprout exactly two
branches; no branches are grown from the terminal nodes. And most
important: there are no intersecting branches. We will alk about more
general structures later (called list-structures or directed graphs).
Here are some binary tres:
A
1 2 B NIL
A D E
B C
Perhaps you can see how to interpret S-exprs now. The atoms are
interpreted as terminal nodes; and since non-atomic S-exprs always
have two branches (oops, two sub-expressions) we can write the first
sub-expression as the left branch of a binary tree and the second sub-
expression as the right branch. For example:
(A . B) (A . (B . C))
A
A B B C
((A . B) . C) (A . (B . NIL))
C A
A B B NIL
Other representations of binary trees which will be more suggestive when
we talk about implementation of LISP are:
(A . (B . C))
---------- --------- ----------- ---------
≡ | A | | = | | |--> | | | ≡ | |
---------- --------- ----------- ---------
| A B C | |
∨ ∨ ∨
---------- A ----------
| B | C | | |
---------- | |
----------
| |
∨ ∨
B C
NOTE THAT THE TRANSLATION PROCESS IS INHERENTLY RECURSIVE.
So much for the domain of objects; what we need now are some functions
or operators to perform oprations on the domain. First such function is the
cons (construct) function wwich is used to generate s-exprs from less
complicated s-exprs. cons is a total function, that is it is defined for all
sexpr arguments. It is a function of two arguments and has as value a
new sexpr interpreted as a binary tree with left branch as the first argument
and with right branch, the second argument. For example:
cons [A; B] = (A . B)
cons [(A . B); C] = ((A . B) .C)
We have two functions for traversing binary trees. They are both partial functions;
that is they are (unary) functions which are undefined for atomic arguments.
Car returns as vaaue the first subexpression of its (composite) argument; cdr
(pronounced could-er) returns as vlue the second sub-expression of its
argument. For example:
car [(A . B)] = A car [A] is undefined.
cdr [(A . B)] = B cdr [A(A . (B . C))] = (B . C)
car [((A . B) . C)] = (A . B)
As with most mathematical theories, we will allow functional composition.
car [cdr [(A . (B . C))]] = B = cdr [cdr [(A . (C . B))]]
car [cons [x;y]] = x;cdr [cons [x;y]] = y .
Notice that in the last two examples we have introduced variables (over
S-exprs). In the sequel lower-case letters (or lower-case identifiers) will be
used freely as (sexpr) variables. So for example y is an atom; x is a variable
The composition of many car and cdr functions occurs so frequently that an
abbreviation has been developed. For example:
cadr [x] ≡ car [cdr [x]]
caddr [x] ≡ car [cdr[cdr [x]]]
cdar [x] ≡ cdr [car [x]]
These compositions are also called "car-cdr" chains, and are useful in
traversing binary trees.
We cannot generate a very exciting theory based simply on car, cdr, and cons
with functional composition. Before we can write reasonably interesting
algorithms we must have some way of performing conditional actions;
an IF-THEN-ELSE facility if you wish. To do this we need predicates: functions
returning a value representing truth or falsity. Since our functions
return Sexprs as values we must represent truth and falsity as Sexprs.
We will take the atoms T and NIL to represent true and false, respectively.
Now two predicates of one argument return T or NIL depending on whether or not that
argument is atomic.
atom [A] ≡ atom [NIL] = T
atom [atom [A]] = T = atom [atom [(A . B)]]
The second primtive predicate is named eq. It is a binary predicate defined
only if its arguments are both atomic. It returns T if the arguments are the
same atom; it returns NIL otherwise.
eq [A;A] = T eq [A;B] = NIL
eq [(A . B); A] is undefined, as is eq [(A . B);(A . B)]
eq [eq [A;B]; eq[C;D]] = T
The IF-THEN-ELSE operation in LISP is called the condition expression. It
is written:
[p → e ; p → e ... p → e ]
1 1 2 2 n n
The meaning (or semantics) of conditionals is: Each p is a predicate; each e
i i
is an expression. We evalue the p 's from left to right, finding the first
i
which returns value T. When we find such a p , we evaluate the corresponding
i
e . The value of the conditional expression the value returned by e ; if none
i i
of the p 's are true then the conditional expression is undefined. The
i
conditional conditional expression is also undefined if we come across a P
i
which is undefined. Examples:
[atom [A] → B; eq [A;(A . B)] → C] = B
[eq [A;(A . B)] → C; atom [A] → B] is undefined
[atom [(A . B)] → B; eq [A ; B] → C; eq [car[(A . B)];
cdr[(B . A)]] → E] = E
In applications of conditional expressions it is often convenient to be
assured that the conditional always is defined. To make sure that at least on of
the p 's is true we can pick a predicate for p , (the last predicatee in the
i n
conditional) which is always true. You can think of lots of predicates which
are always true ( for example, eq [1 ; 1] ). A natural predicate is the
constant predicate, T. Thus:
[p + e ; T → e ]
1 1 2
can be read: If p is true then e else e . (or otherwise e )
1 1 2 2
A word to the wise. It doesn't seem like you can do much damage with such
a limited collection of operations. Do not be deceived! In elementary number
all you have is zero and some simple functions, and elementary number theory
is far from elementary.
For example; our predicate eq is defined only for atomic arguments. We would like
to be able to test for equality of arbitrary sexprs. For example:
equal [(A . B);(A . B)] = T = equal [A,A]
equal [(A . B);(B . A)] = NIL , equal [(A . (B . C));
(A . (B . C))] = T
Here's an intuitive description of such a function (predicate named equal).
1. if both arguments are atomic then see what eq says about them
(are they "eq"). We make sure that they are both atomic by using atom
and a conditional expression.
2. If one is atomic and the other is not they can't be equal s-exprs.
3. Otherwise both are non-atomic sexprs. Both have two sub-expressions.
Look at both first subexpressions. If the first sub-expressions are not
equal then certainly the initial expressions cannot hope to be equal.
However, if the first subexpressions are equal then the question of
whether or not the initial expressions are equal depends on the
equality ( or non-equality) of the second subexpressions. Thus the
following definition:
equal[x,y] = [atom[x] → [atom[y] → eq [x,y]
T→ NIL]
equal [car[x];car[y]] → equal[cdr[x];cdr[y]]
T → NIL]
LIST NOTATION
In many applications of LISP it will be very convenient to represent
sequences. E.g. (X ,X ,X ,X ,X ,X ). We will allow sequences to have
1 2 3 4 5 6
sub-sequences (to an arbitrary depth) e.g. (A,(B,C),D,(E,B)). The obvious
question is how to represent sequences as Sexprs. Since sequences can be of
arbitrary length any representation must include an unambiguous way of
determining the end of such a sequence. The choice we make is represented
graphically as follows:
---------- ----------- -----------
| | |--> | | | --> | | | ≡ (X . (X . (X . NIL)))
---------- ----------- ----------- 1 2 3
X X X NIL
1 2 3
Note that we can determine the end of the sequence using the predicate:
endofseq[x] = [atom[x] → eq[x,NIL]; T → NIL]
That is the right-hand branch in any binary tree representing a sequence
will always point to the rest of the sequence or will be the atom NIL. It
is not by accident that the atom NIL is used for falsity and the termination
symbol for sequences. You should become fluent in translating between
sexpr-notation and sequence notation.
In standord Computer Science terminology sequences are called lists, thus we
will refer usually to list-notation list terminator, etc. You should also
become fluent in applying our basic functions to lists without having to
translate back to sexpr-notation.
A final point: what about the empty sequence or empty list? Looking at the
graphical interpretation of a sequence it appears natural to take NIL as
the empty list since after you have removed all the elements from the list,
NIL, the list terminator is all that is left. Also from the standpoint of
sequence notation, the empty sequence is represented as: "( )". To be
consistent, then, we will define ( ) to be the same as the atom NIL. And
a notational point: in graphical notation it is often convenient to write
--------- ----------
| | | as | | | . Thus for
--------- ----------
NIL
example:
(A,(B,C),D) is:
---------- ----------- -----------
| | | --> | | | --> | | |
---------- ----------- ----------- .
A | D
| ------- --------
|--| | |------| | |
------- --------
B C
or:
and finally in list-notation, the commas can be replaced by spaces.
e.g. (A,(B,C),D) ≡ (A(B C)D).
Note: the "dots" in dot-notation are never optional.
Problems
I Which of the following are dotted-pairs.
1 (X . Y) 2 ((A .(B . C)) 3 A2 4 (X . Y2 . Z)
II Write the following as binary trees.
1 ((A . B).(B . (C . D))) 2 (((A . B).C).E)
3 ((X . NIL).(Y .(Z . NIL))) 4 (NIL . NIL)
III Write the following binary trees as Sexprs.
1. /\ 2 -------- 3 --------
/ /\ | A | | | | |
A / \ -------- --------
B C \ A \
-------- --------
| B | | | | |
-------- --------
/ \ B \
-------- --------- --------
|C |NIL| | D | E | | | |
-------- --------- --------
C NIL
4 -------- -------- 5 --------- -------- --------
|CAR| |--→| |NIL| | | |-→| | |-→| | |
-------- --------- --------- -------- --------
| ------- -------- CONS X Y NIL
→| | |-→| | |
------- --------
QUOTE A NIL
IV Evaluate the following
1. eq[X;Y] 2. cons[X;Y] 3. car[(X . Y)] 4. car[cons[X;Y]]
5. cadr[(X .(Y . NIL))] 6. cdar[(X .(Y . NIL))]
7. eq[cdr[(A . B)];cdr[(C . B)]] 8. atom[cons[(A . B);(C . D)]]
9. cons[atom[A];atom[(A . B)]] 10. eq[atom[ATOM];atom[EQ]]
11. [T → A; T → B] 12. [NIL → A; T → B] 13. [eq[A;B] → 4]
14. [atom[X] → atom[X]; T → FOO] 15. [eq[EQ;X] → A; eq[A;B] → B; T → C]
16. cons[[eq[A;B] → 1; T → FOO];cons[A;cadr[(A .(B .C))]]]
V Use the following definition:
twist[s] <== [atom[s] → s; T → cons[twist[cdr[s]];twist[car[s]]]]
and evaluate: 1. twist[A] 2. twist[(A . B)] 3. twist[((A . B). C)]
Now try: findem[x;y] <== [atom[x] → [eq[x;y] → T; T → NIL];
T → cons[findem[car[x];y];findem[cdr[x];y]]]
and evaluate: 1. findem[(A . B);A] 2. findem[(B .(A . C));A]
3. findem[(B .(A . C));C] 4. findem[(A . B);(A . B)]
PROBLEMS INVOLVING LIST-NOTATION
VI Translate the following lists into Sexpr dotted-pair notation.
1. (A B C) 2.(A) 3. ((A)) 4. (A (B (C))).
Now go the other way and translate the following sexprs into list notation.
5. ((A .(B . NIL)).((C . NIL). NIL)) 6. (NIL . NIL)
7. ((CONS .((QUOTE .(A . NIL)). NIL))
VII Evaluate the following, writing the results in list notation where possible.
1. car[(A B)] 2. cdr[(A B)] 3. cons[A;(B C)] 4. cons[A;NIL]
5. cons[eq[A;A];(A B C)]
VIII Use the following defintion:
match[k;m] <== [null[k] → NO;
null[m] → NO;
eq[car[k];car[m]] → car[k];
T → match[cdr[k];cdr[m]]]
and evaluate:
1. match[(X);(X)] 2. match[(A B E);(J O E)] 3. match[(F O O); (BAZ)]
IX Now write your own.
1. among[x;y] <== ... ; among is to be a predicate; x is an atom; y is a list
of atoms. among is to return NIL if x is not found as an element of y; o.w.
among is to return T.
e.g. among[A;(A B C)] = among[A;(C D E A)] = T
among[A1;(A2 B2)] = NIL.
2. anywhere[x;y] <== ...; anywhere is a predicate; x is an atom; y is an arbitrary
sexpr. anywhere is to return T just in the case that x appears somewhere in y.
e.g. anywhere[A;(A B C)] = anywhere[A;((A . B). C)] = T
anywhere[A;(B C D)] = NIL.